5716. Карточные домики

Славик мечтает стать артистом оригинального жанра, поэтому постоянно занимается манипуляциями с разнообразными предметами. В данный момент он всё своё свободное время занят построением карточных домиков. Ему уже даже удалось построить в домашних условиях 4-х этажный домик, на что у него ушло 26 карт. А на уроке технологии ему удалось тайком от учителя продемонстрировать своё умение одноклассникам и построить домик в 3 этажа, на что было потрачено всего 15 карт. “Художества” будущего артиста запечатлены на фотографиях из его мобильного телефона ниже.

В данный момент Славика интересует вопрос математического содержания: А сколько нужно иметь карт, чтобы построить домик в n этажей? Он просит Вас помочь ему, так как с математикой у Славика пока проблемы...

Вход. Целое неотрицательное число n – количество этажей в домике, который планируется построить. Известно, что это число не превышает 10⁸.

Выход. Вывести количество карт, необходимое для постройки домика в n этажей.

Пример входа	Пример выхода
3	15

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Пусть f(h) равно количеству карт, из которых можно построить карточный домик высоты h. Например, f(1) = 2, f(2) = 7, f(3) = 15.

Для построения домика высоты h у основания следует поставить h домиков высоты 1 (2h карт) и h – 1 перекрытий. На основание ставится домик высоты h – 1, на что потребуется f(h – 1) карт. Отсюда f(h) = 2h + h – 1 + f(h – 1) или

f(h) = 3h – 1 + f(h – 1)

Выведем явную формулу.

f(h) = 3h – 1 + 3(h – 1) – 1 + 3(h – 2) – 1 + … + 3 * 1 – 1 =

= 3 (h + (h – 1) + (h – 2) + … + 1) – h =

= = =

Пример

Для домика высоты 1 достаточно 2 карты. Для домика высоты 2 необходимо 7 карт. Домик высоты 3 можно построить из 15 карт.

Реализация алгоритма

Читаем высоту домика n. Вычисляем и выводим количество карт в нем.

scanf("%lld", &n);

res = n * (3 * n + 1) / 2;

printf("%lld\n", res);